package pageReplacement;

import java.util.Scanner;

public class PageReplacement {
    static Scanner scanner=new Scanner(System.in);
    int[][] blocks=new int[3][100];
    int[] pages=new int[100];
    String[] shotInfo=new String[100];
    int page;

    public static void main(String[] args) {
        PageReplacement.menu();
        while(scanner.hasNext()){
            PageReplacement pageReplacement=new PageReplacement();
            String sleId=scanner.next();
            switch (sleId){
                case "1":
                    System.out.println("请输入将要访问的页面数:");
                    if(scanner.hasNext())
                        pageReplacement.page=scanner.nextInt();
                    System.out.println("请分别输入将要访问的"+pageReplacement.page+"张页面的编号(以空格分隔):");
                    for(int i=0;i<pageReplacement.page;i++){
                        pageReplacement.pages[i]=scanner.nextInt();
                    }
                    System.out.println("最佳置换算法执行页面置换情况如下表所示:\n");
                    pageReplacement.optimalReplacement();
                    pageReplacement.printInfo();
                    System.out.println("\n\n请继续选择(1.OPT 2.FIFO 3.LRU 0.退出): ");
                    break;
                case "2":
                    System.out.println("请输入将要访问的页面数:");
                    if(scanner.hasNext())
                        pageReplacement.page=scanner.nextInt();
                    System.out.println("请分别输入将要访问的"+pageReplacement.page+"张页面的编号(以空格分隔):");
                    for(int i=0;i<pageReplacement.page;i++){
                        pageReplacement.pages[i]=scanner.nextInt();
                    }
                    System.out.println("FIFO置换算法执行页面置换情况如下表所示:\n");
                    pageReplacement.fifoReplacement();
                    pageReplacement.printInfo();
                    System.out.println("\n\n请继续选择(1.OPT 2.FIFO 3.LRU 0.退出): ");
                    break;
                case "3":
                    System.out.println("请输入将要访问的页面数:");
                    if(scanner.hasNext())
                        pageReplacement.page=scanner.nextInt();
                    System.out.println("请分别输入将要访问的"+pageReplacement.page+"张页面的编号(以空格分隔):");
                    for(int i=0;i<pageReplacement.page;i++){
                        pageReplacement.pages[i]=scanner.nextInt();
                    }
                    System.out.println("LRU置换算法执行页面置换情况如下表所示:\n");
                    pageReplacement.lruReplacement();
                    pageReplacement.printInfo();
                    System.out.println("\n\n请继续选择(1.OPT 2.FIFO 3.LRU 0.退出): ");
                    break;
                case "0":
                    break;
                default:
                    System.out.println("请输入正确的数字!");
                    break;
            }
            if(sleId.equals("0")) {
                break;
            }
        }
        scanner.close();
    }

    public static void menu(){
        System.out.println("********页面置换算法选择(物理块数为三)********");
        System.out.println("         1.最佳置换算法(OPT)              ");
        System.out.println("         2.先进先出置换算法(FIFO)         ");
        System.out.println("         3.最近最久未使用算法(LRU)         ");
        System.out.println("         0.退出(exit)                    ");
        System.out.println("*******************************************");
        System.out.println("请输入相应数字选择(0~3): ");
    }

    public void optimalReplacement(){
        int[] timeIn =new int[100];
        int[] length=new int[3];
        for(int i=0;i<page;i++){
            if (i == 0) {
                blocks[0][i]=-1;
                blocks[1][i]=-1;
                blocks[2][i]=-1;
            }
            if(i>0){
                blocks[0][i]=blocks[0][i-1];
                blocks[1][i]=blocks[1][i-1];
                blocks[2][i]=blocks[2][i-1];
            }
            for(int j=0;j<3;j++){
                if(pages[i]==blocks[j][i]){
                    shotInfo[i]="命中";
                    break;
                } else
                    shotInfo[i]="缺页";
            }
            //更新内存块中页面驻留时间
            for(int k=0;k<3;k++){
                if(blocks[k][i]>=0)
                    timeIn[blocks[k][i]]++;
            }
            //选择要调入的页
            if(shotInfo[i].equals("缺页")){
                if(blocks[0][i]==-1){
                    blocks[0][i]=pages[i];
                    continue;
                }else if(blocks[1][i]==-1){
                    blocks[1][i]=pages[i];
                    continue;
                }else if(blocks[2][i]==-1){
                    blocks[2][i]=pages[i];
                    continue;
                }

                int x=0;
                while(x<3){
                    for(int k=i;k<page;k++){
                        if(blocks[x][i]==pages[k]){
                            length[x]=k;
                            break;
                        }
                    }
                    x++;
                }
                //如果有多个页面将来一段时间不用，则将驻留时间最久的页面置换出去，并更新驻留时间
                if(length[0]!=0&&length[1]!=0&&length[2]!=0){
                    if(length[0]>length[1]&&length[0]>length[2]){
                        timeIn[blocks[0][i]]=0;
                        blocks[0][i]=pages[i];
                    } else if(length[1]>length[0]&&length[1]>length[2]){
                        timeIn[blocks[1][i]]=0;
                        blocks[1][i]=pages[i];
                    } else if(length[2]>length[0]&&length[2]>length[1]){
                        timeIn[blocks[2][i]]=0;
                        blocks[2][i]=pages[i];
                    }
                } else if(length[0]!=0&&length[1]!=0&&length[2]==0){
                    timeIn[blocks[2][i]]=0;
                    blocks[2][i]=pages[i];
                } else if(length[0]!=0&&length[1]==0&&length[2]!=0){
                    timeIn[blocks[1][i]]=0;
                    blocks[1][i]=pages[i];
                } else if(length[0]==0&&length[1]!=0&&length[2]!=0){
                    timeIn[blocks[0][i]]=0;
                    blocks[0][i]=pages[i];
                } else if(length[0]==0&&length[1]==0&&length[2]!=0){
                    if(timeIn[blocks[0][i]]>timeIn[blocks[1][i]]){
                        timeIn[blocks[0][i]]=0;
                        blocks[0][i]=pages[i];
                    }else{
                        timeIn[blocks[1][i]]=0;
                        blocks[1][i]=pages[i];
                    }
                }else if(length[0]==0&&length[1]!=0&&length[2]==0){
                    if(timeIn[blocks[0][i]]>timeIn[blocks[2][i]]){
                        timeIn[blocks[0][i]]=0;
                        blocks[0][i]=pages[i];
                    }else{
                        timeIn[blocks[2][i]]=0;
                        blocks[2][i]=pages[i];
                    }
                }else if(length[0]!=0&&length[1]==0&&length[2]==0){
                    if(timeIn[blocks[1][i]]>timeIn[blocks[2][i]]){
                        timeIn[blocks[1][i]]=0;
                        blocks[1][i]=pages[i];
                    }else{
                        timeIn[blocks[2][i]]=0;
                        blocks[2][i]=pages[i];
                    }
                }else{
                    if(timeIn[blocks[0][i]]>timeIn[blocks[1][i]]&&timeIn[blocks[0][i]]>timeIn[blocks[2][i]]){
                        timeIn[blocks[0][i]]=0;
                        blocks[0][i]=pages[i];
                    }else if(timeIn[blocks[1][i]]>timeIn[blocks[0][i]]&&timeIn[blocks[1][i]]>timeIn[blocks[2][i]]){
                        timeIn[blocks[1][i]]=0;
                        blocks[1][i]=pages[i];
                    }else if(timeIn[blocks[2][i]]>timeIn[blocks[0][i]]&&timeIn[blocks[2][i]]>timeIn[blocks[1][i]]){
                        timeIn[blocks[2][i]]=0;
                        blocks[2][i]=pages[i];
                    }
                }
                length[0]=0;
                length[1]=0;
                length[2]=0;
            }
        }
    }

    public void fifoReplacement(){
        int[] timeIn =new int[100];
        for(int i=0;i<page;i++){
            if (i == 0) {
                blocks[0][i]=-1;
                blocks[1][i]=-1;
                blocks[2][i]=-1;
            }
            if(i>0){
                blocks[0][i]=blocks[0][i-1];
                blocks[1][i]=blocks[1][i-1];
                blocks[2][i]=blocks[2][i-1];
            }
            for(int j=0;j<3;j++){
                if(pages[i]==blocks[j][i]){
                    shotInfo[i]="命中";
                    break;
                } else
                    shotInfo[i]="缺页";
            }
            //更新内存块中页面驻留时间
            for(int k=0;k<3;k++){
                if(blocks[k][i]>=0)
                    timeIn[blocks[k][i]]++;
            }
            //选择要调入的页
            if(shotInfo[i].equals("缺页")){
                if(blocks[0][i]==-1){
                    blocks[0][i]=pages[i];
                    continue;
                }else if(blocks[1][i]==-1){
                    blocks[1][i]=pages[i];
                    continue;
                }else if(blocks[2][i]==-1){
                    blocks[2][i]=pages[i];
                    continue;
                }

                if(timeIn[blocks[0][i]]>timeIn[blocks[1][i]]&&timeIn[blocks[0][i]]>timeIn[blocks[2][i]]){
                    timeIn[blocks[0][i]]=0;
                    blocks[0][i]=pages[i];
                }else if(timeIn[blocks[1][i]]>timeIn[blocks[0][i]]&&timeIn[blocks[1][i]]>timeIn[blocks[2][i]]){
                    timeIn[blocks[1][i]]=0;
                    blocks[1][i]=pages[i];
                }else if(timeIn[blocks[2][i]]>timeIn[blocks[0][i]]&&timeIn[blocks[2][i]]>timeIn[blocks[1][i]]){
                    timeIn[blocks[2][i]]=0;
                    blocks[2][i]=pages[i];
                }

            }

        }
    }

    public void lruReplacement(){
        int[] timeIn =new int[100];
        for(int i=0;i<page;i++){
            if (i == 0) {
                blocks[0][i]=-1;
                blocks[1][i]=-1;
                blocks[2][i]=-1;
            }
            if(i>0){
                blocks[0][i]=blocks[0][i-1];
                blocks[1][i]=blocks[1][i-1];
                blocks[2][i]=blocks[2][i-1];
            }
            for(int j=0;j<3;j++){
                if(pages[i]==blocks[j][i]){
                    shotInfo[i]="命中";
                    break;
                } else
                    shotInfo[i]="缺页";
            }
            //更新内存块中页面驻留时间
            for(int k=0;k<3;k++){
                if(blocks[k][i]>=0)
                    timeIn[blocks[k][i]]++;
            }
            //选择要调入的页
            if(shotInfo[i].equals("缺页")){
                if(blocks[0][i]==-1){
                    blocks[0][i]=pages[i];
                    continue;
                }else if(blocks[1][i]==-1){
                    blocks[1][i]=pages[i];
                    continue;
                }else if(blocks[2][i]==-1){
                    blocks[2][i]=pages[i];
                    continue;
                }

                if(timeIn[blocks[0][i]]>timeIn[blocks[1][i]]&&timeIn[blocks[0][i]]>timeIn[blocks[2][i]]){
                    timeIn[blocks[0][i]]=0;
                    blocks[0][i]=pages[i];
                }else if(timeIn[blocks[1][i]]>timeIn[blocks[0][i]]&&timeIn[blocks[1][i]]>timeIn[blocks[2][i]]){
                    timeIn[blocks[1][i]]=0;
                    blocks[1][i]=pages[i];
                }else if(timeIn[blocks[2][i]]>timeIn[blocks[0][i]]&&timeIn[blocks[2][i]]>timeIn[blocks[1][i]]){
                    timeIn[blocks[2][i]]=0;
                    blocks[2][i]=pages[i];
                }
            }
            //刷新页面自上次访问以来经过的时间t
            if(shotInfo[i].equals("命中")){
                int x=0;
                while(x<=2){
                    if(blocks[x][i]==pages[i])
                        timeIn[blocks[x][i]]=0;
                    x++;
                }
            }
        }
    }

    public void printInfo(){
        System.out.print("页面走向:  ");
        for(int i=0;i<page;i++)
            System.out.printf("%-5d",pages[i]);
        System.out.println();
        for(int i=0;i<3;i++){
            if(i==0)
                System.out.print("物理块一:  ");
            else if(i==1)
                System.out.print("物理块二:  ");
            else if(i==2)
                System.out.print("物理块三:  ");
            for(int j=0;j<page;j++){
                if(blocks[i][j]!=-1)
                    System.out.printf("%-5d",blocks[i][j]);
                else
                    System.out.printf("     ");
            }
            System.out.println();
        }

        System.out.print("缺页中断:  ");
        for(int i=0;i<page;i++)
            if(shotInfo[i].equals("缺页"))
                System.out.printf("%-5s","X");
            else
                System.out.printf("     ");
    }
}
